import sun.reflect.generics.tree.Tree;

import java.util.Stack;

public class TreeNode {

    public TreeNode root;

    public TreeNode left;
    public TreeNode right;
    public int val;
    public TreeNode(int val){
        this.val=val;
    }

    public void creatTree(){
        root = new TreeNode(1);
        TreeNode B = new TreeNode(2);
        TreeNode C = new TreeNode(3);
        root.left=B;
        root.right=C;

        TreeNode D=new TreeNode(4);
        TreeNode E=  new TreeNode(5);
        B.left=D;
        B.right=E;
        TreeNode F = new TreeNode(6);
        TreeNode G = new TreeNode(7);
        C.left=F;
        C.right=G;
        TreeNode H=new TreeNode(8);
        E.right=H;

    }
    public static void PrioTree(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        if(node==null){
            return;
        }
        stack.push(node);
        System.out.print(node.val+" ");
        TreeNode cur = node;
        while(!stack.empty()) {
            if(cur==node){
                stack.pop();
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
            System.out.print(stack.peek().val+" ");
            cur = stack.pop();
        }



    }

    public static void first(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = node;
        if (node == null) {
            return;
        }
        while (cur != null || !stack.empty()){
            while (cur != null) {
                System.out.print(cur.val + " ");
                stack.push(cur);
                cur = cur.left;
            }
        TreeNode tmp = stack.pop();
        cur = tmp.right;
    }

    }

    public static void center(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        if(node==null){
            return;
        }
        TreeNode cur = node;
        while(cur!=null||!stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode tmp = stack.pop();
            System.out.print(tmp.val + " ");
            cur = tmp.right;
        }
    }

    public static void  finall(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        if(node==null){
            return;
        }
        TreeNode cur = node;
        TreeNode prev = null;
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode tmp = stack.peek();
            if(tmp.right==null||tmp.right==prev){
                System.out.print(tmp.val+" ");
                prev=tmp;
                stack.pop();
            }
            else{
                cur=tmp.right;
            }
        }
    }
    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.creatTree();
       finall(node.root);
    }
}
